home *** CD-ROM | disk | FTP | other *** search
/ Aminet 8 / Aminet 8 (1995)(GTI - Schatztruhe)[!][Oct 1995].iso / Aminet / dev / gcc / gcc270cp.lha / gnu / lib / g++-include / BitSet.h < prev    next >
C/C++ Source or Header  |  1995-07-28  |  9KB  |  369 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17. */
  18.  
  19. #ifndef _BitSet_h
  20. #ifdef __GNUG__
  21. #pragma interface
  22. #endif
  23.  
  24. #define _BitSet_h 1
  25.  
  26. #include <iostream.h>
  27. #include <limits.h>
  28.  
  29. #undef OK
  30.  
  31. #define BITSETBITS  (sizeof(short) * CHAR_BIT)
  32.  
  33. struct BitSetRep
  34. {
  35.   unsigned short  len;          // number of shorts in s
  36.   unsigned short  sz;           // allocated slots
  37.   unsigned short  virt;         // virtual 0 or 1
  38.   unsigned short  s[1];         // bits start here
  39. };
  40.  
  41. extern BitSetRep*   BitSetalloc(BitSetRep*, const unsigned short*, 
  42.                                 int, int, int);
  43. extern BitSetRep*   BitSetcopy(BitSetRep*, const BitSetRep*);
  44. extern BitSetRep*   BitSetresize(BitSetRep*, int);
  45. extern BitSetRep*   BitSetop(const BitSetRep*, const BitSetRep*, 
  46.                              BitSetRep*, char);
  47. extern BitSetRep*   BitSetcmpl(const BitSetRep*, BitSetRep*);
  48.  
  49.  
  50. extern BitSetRep    _nilBitSetRep;
  51.  
  52. class BitSet;
  53.  
  54. class BitSetBit
  55. {
  56. protected:
  57.   BitSet*            src;
  58.   unsigned long      pos;
  59.  
  60.  public:
  61.                      BitSetBit(BitSet* v, int p);
  62.                      BitSetBit(const BitSetBit& b);
  63.                     ~BitSetBit();
  64.                      operator int() const;
  65.   int                operator = (int b);
  66.   int                operator = (const BitSetBit& b);
  67. };
  68.  
  69. class BitSet
  70. {
  71. protected:
  72.   BitSetRep*          rep;
  73.  
  74.   
  75. public:
  76.  
  77. // constructors
  78.                      BitSet();
  79.                      BitSet(const BitSet&);
  80.  
  81.                     ~BitSet();
  82.  
  83.   BitSet&            operator =  (const BitSet& y);
  84.  
  85. // equality & subset tests
  86.  
  87.   friend int         operator == (const BitSet& x, const BitSet& y);
  88.   friend int         operator != (const BitSet& x, const BitSet& y);
  89.   friend int         operator <  (const BitSet& x, const BitSet& y);
  90.   friend int         operator <= (const BitSet& x, const BitSet& y);
  91.   friend int         operator >  (const BitSet& x, const BitSet& y);
  92.   friend int         operator >= (const BitSet& x, const BitSet& y);
  93.  
  94.  
  95. // operations on self
  96.  
  97.   BitSet&            operator |= (const BitSet& y);
  98.   BitSet&            operator &= (const BitSet& y);
  99.   BitSet&            operator -= (const BitSet& y);
  100.   BitSet&            operator ^= (const BitSet& y);
  101.  
  102.   void               complement();
  103.  
  104. // individual bit manipulation
  105.  
  106.   void               set(int pos);
  107.   void               set(int from, int to);
  108.   void               set(); // set all
  109.  
  110.   void               clear(int pos);
  111.   void               clear(int from, int to);
  112.   void               clear(); // clear all
  113.  
  114.   void               invert(int pos);
  115.   void               invert(int from, int to);
  116.  
  117.   int                test(int pos) const;
  118.   int                test(int from, int to) const;
  119.  
  120.   BitSetBit          operator [] (int i);
  121.   
  122. // iterators
  123.  
  124.   int                first(int b = 1) const;
  125.   int                last(int b = 1) const;
  126.  
  127.   int                next(int pos, int b = 1) const;
  128.   int                prev(int pos, int b = 1) const;
  129.   int                previous(int pos, int b = 1) const /* Obsolete synonym */
  130.     { return prev(pos, b); }
  131.  
  132. // status
  133.  
  134.   int                empty() const;
  135.   int                virtual_bit() const;
  136.   int                count(int b = 1) const;
  137.   
  138. // convertors & IO
  139.  
  140.   friend BitSet      atoBitSet(const char* s, 
  141.                                char f='0', char t='1', char star='*');
  142.   // BitSettoa is deprecated; do not use in new programs.
  143.   friend const char* BitSettoa(const BitSet& x, 
  144.                                char f='0', char t='1', char star='*');
  145.  
  146.   friend BitSet      shorttoBitSet(unsigned short w);
  147.   friend BitSet      longtoBitSet(unsigned long w);
  148.  
  149.   friend ostream&    operator << (ostream& s, const BitSet& x);
  150.   void             printon(ostream& s,
  151.                  char f='0', char t='1', char star='*') const;
  152.  
  153. // procedural versions of operators
  154.  
  155.   friend void        and(const BitSet& x, const BitSet& y, BitSet& r);
  156.   friend void        or(const BitSet& x, const BitSet& y, BitSet& r);
  157.   friend void        xor(const BitSet& x, const BitSet& y, BitSet& r);
  158.   friend void        diff(const BitSet& x, const BitSet& y, BitSet& r);
  159.   friend void        complement(const BitSet& x, BitSet& r);
  160.  
  161. // misc
  162.  
  163.   void      error(const char* msg) const;
  164.   int                OK() const;
  165. };
  166.  
  167.  
  168. typedef BitSet BitSetTmp;
  169.  
  170. // These are inlined regardless of optimization
  171.  
  172. inline int BitSet_index(int l)
  173. {
  174.   return (unsigned)(l) / BITSETBITS;
  175. }
  176.  
  177. inline int BitSet_pos(int l)
  178. {
  179.   return l & (BITSETBITS - 1);
  180. }
  181.  
  182.  
  183. inline BitSet::BitSet() : rep(&_nilBitSetRep) {}
  184.  
  185. inline BitSet::BitSet(const BitSet& x) :rep(BitSetcopy(0, x.rep)) {}
  186.  
  187. inline BitSet::~BitSet() { if (rep != &_nilBitSetRep) delete rep; }
  188.  
  189. inline BitSet& BitSet::operator =  (const BitSet& y)
  190. { 
  191.   rep = BitSetcopy(rep, y.rep);
  192.   return *this;
  193. }
  194.  
  195. inline int operator != (const BitSet& x, const BitSet& y) { return !(x == y); }
  196.  
  197. inline int operator >  (const BitSet& x, const BitSet& y) { return y < x; }
  198.  
  199. inline int operator >= (const BitSet& x, const BitSet& y) { return y <= x; }
  200.  
  201. inline void and(const BitSet& x, const BitSet& y, BitSet& r)
  202. {
  203.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '&');
  204. }
  205.  
  206. inline void or(const BitSet& x, const BitSet& y, BitSet& r)
  207. {
  208.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '|');
  209. }
  210.  
  211. inline void xor(const BitSet& x, const BitSet& y, BitSet& r)
  212. {
  213.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '^');
  214. }
  215.  
  216. inline void diff(const BitSet& x, const BitSet& y, BitSet& r)
  217. {
  218.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '-');
  219. }
  220.  
  221. inline void complement(const BitSet& x, BitSet& r)
  222. {
  223.   r.rep = BitSetcmpl(x.rep, r.rep);
  224. }
  225.  
  226. #if defined(__GNUG__) && !defined(_G_NO_NRV)
  227.  
  228. inline BitSet operator & (const BitSet& x, const BitSet& y) return r
  229. {
  230.   and(x, y, r);
  231. }
  232.  
  233. inline BitSet operator | (const BitSet& x, const BitSet& y) return r
  234. {
  235.   or(x, y, r);
  236. }
  237.  
  238. inline BitSet operator ^ (const BitSet& x, const BitSet& y) return r
  239. {
  240.   xor(x, y, r);
  241. }
  242.  
  243. inline BitSet operator - (const BitSet& x, const BitSet& y) return r
  244. {
  245.   diff(x, y, r);
  246. }
  247.  
  248. inline BitSet operator ~ (const BitSet& x) return r
  249. {
  250.   ::complement(x, r);
  251. }
  252.  
  253. #else /* NO_NRV */
  254.  
  255. inline BitSet operator & (const BitSet& x, const BitSet& y) 
  256. {
  257.   BitSet r; and(x, y, r); return r;
  258. }
  259.  
  260. inline BitSet operator | (const BitSet& x, const BitSet& y) 
  261. {
  262.   BitSet r; or(x, y, r); return r;
  263. }
  264.  
  265. inline BitSet operator ^ (const BitSet& x, const BitSet& y) 
  266. {
  267.   BitSet r; xor(x, y, r); return r;
  268. }
  269.  
  270. inline BitSet operator - (const BitSet& x, const BitSet& y) 
  271. {
  272.   BitSet r; diff(x, y, r); return r;
  273. }
  274.  
  275. inline BitSet operator ~ (const BitSet& x) 
  276. {
  277.   BitSet r; ::complement(x, r); return r;
  278. }
  279.  
  280. #endif
  281.  
  282. inline BitSet& BitSet::operator &= (const BitSet& y)
  283. {
  284.   and(*this, y, *this);
  285.   return *this;
  286. }
  287.  
  288. inline BitSet& BitSet::operator |= (const BitSet& y)
  289. {
  290.   or(*this, y, *this);
  291.   return *this;
  292. }
  293.  
  294. inline BitSet& BitSet::operator ^= (const BitSet& y)
  295. {
  296.   xor(*this, y, *this);
  297.   return *this;
  298. }
  299.  
  300. inline BitSet& BitSet::operator -= (const BitSet& y)
  301. {
  302.   diff(*this, y, *this);
  303.   return *this;
  304. }
  305.  
  306.  
  307. inline void BitSet::complement()
  308. {
  309.   ::complement(*this, *this);
  310. }
  311.  
  312. inline int BitSet::virtual_bit() const
  313. {
  314.   return rep->virt;
  315. }
  316.  
  317. inline int BitSet::first(int b) const
  318. {
  319.   return next(-1, b);
  320. }
  321.  
  322. inline int BitSet::test(int p) const
  323. {
  324.   if (p < 0) error("Illegal bit index");
  325.   int index = BitSet_index(p);
  326.   return (index >= rep->len)? rep->virt : 
  327.          ((rep->s[index] & (1 << BitSet_pos(p))) != 0);
  328. }
  329.  
  330.  
  331. inline void BitSet::set()
  332. {
  333.   rep = BitSetalloc(rep, 0, 0, 1, 0);
  334. }
  335.  
  336. inline BitSetBit::BitSetBit(const BitSetBit& b) :src(b.src), pos(b.pos) {}
  337.  
  338. inline BitSetBit::BitSetBit(BitSet* v, int p)
  339. {
  340.   src = v;  pos = p;
  341. }
  342.  
  343. inline BitSetBit::~BitSetBit() {}
  344.  
  345. inline BitSetBit::operator int() const
  346. {
  347.   return src->test(pos);
  348. }
  349.  
  350. inline int BitSetBit::operator = (int b)
  351. {
  352.   if (b) src->set(pos); else src->clear(pos); return b;
  353. }
  354.  
  355. inline int BitSetBit::operator = (const BitSetBit& b)
  356. {
  357.   int i = (int)b;
  358.   *this = i;
  359.   return i;
  360. }
  361.  
  362. inline BitSetBit BitSet::operator [] (int i)
  363. {
  364.   if (i < 0) error("illegal bit index");
  365.   return BitSetBit(this, i);
  366. }
  367.  
  368. #endif
  369.